#include "AFD.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

AFD::AFD(set<char> &alfabeto) : _alfabeto(alfabeto), _ultimo(1), _inicial(0)
{
}

AFD::AFD(const AFND &afnd) : _alfabeto(afnd.alfabeto()), _ultimo(1)
{
    const char lambda = AFND::LAMBDA;
    set<int> actual, destino;
    int actualNum, destinoNum;
    map<set<int>, int> mapEstados;
    stack<set<int> > pila;
    set<int>::iterator itSet;
    set<char>::iterator itAlfa;

    /* Agregamos el estado inicial */
    actual.insert(afnd.inicial());
    actual = afnd.recorrerEstados(actual, lambda);
    _inicial = mapEstados[actual] = nuevoEstado();
    pila.push(actual);

    while (!pila.empty()) {
        actual = pila.top();
        pila.pop();
        actualNum = mapEstados[actual];

        /* Agregamos transiciones */
        for (itAlfa = _alfabeto.begin(); itAlfa != _alfabeto.end(); itAlfa++) {
            destino = afnd.recorrerEstados(actual, *itAlfa);

            if (!destino.empty()) {
                if (mapEstados.find(destino) != mapEstados.end()) {
                    destinoNum = mapEstados[destino];
                } else {
                    destinoNum = mapEstados[destino] = nuevoEstado();
                    pila.push(destino);
                }
                _transiciones[EstadoCaracter(actualNum, *itAlfa)] = destinoNum;
            }

        }

        /* Vemos si es estado final */
        if (!interseccionVacia(actual, afnd.finales()))
            _finales.insert(actualNum);
    }
}

AFD::~AFD()
{
}

bool AFD::interseccionVacia(set<int> first, set<int> second)
{
    set<int> tmp;
    set_intersection(first.begin(), first.end(), second.begin(), second.end(), inserter(tmp, tmp.end()));
    return tmp.empty();
}

int AFD::inicial() const
{
    return this->_inicial;
}

set<char> AFD::alfabeto() const
{
    return this->_alfabeto;
}

set<int> AFD::finales() const
{
    return this->_finales;
}

int AFD::sigma(int e, char c)
{
    if (!esEstado(e))
        return 0;
    AFD::EstadoCaracter ec(e, c);
    return this->_transiciones[ec];
}

int AFD::acepta(string str)
{
    int estado, size, i;

    size = str.size();
    estado = this->inicial();
    for (i = 0; i < size && estado != 0; i++)
        estado = sigma(estado, str[i]);

    return this->esFinal(estado);
}

int AFD::nuevoEstado()
{
    int nuevo = _ultimo++;
    _estados.insert(nuevo);
    return nuevo;
}

int AFD::esFinal(int e)
{
    return this->_finales.find(e) != this->_finales.end();
}

int AFD::esEstado(int e)
{
    return this->_estados.find(e) != this->_estados.end();
}

int AFD::enAlfabeto(char c)
{
    return this->_estados.find(c) != this->_estados.end();
}

int AFD::hacerFinal(int estado)
{
    if (!esEstado(estado))
        return -1;
    this->_finales.insert(estado);
    return 0;
}

int AFD::agregarTransicion(int origen, char caracter, int destino)
{
    if (!esEstado(origen) || !esEstado(destino) || !enAlfabeto(caracter))
        return -1;
    EstadoCaracter ec(origen, caracter);
    this->_transiciones[ec] = destino;
    return 0;
}

ostream& operator<< (ostream &out, AFD &afd)
{
    out << "A = <Q, A, s, q, F>" << endl;

    /* Estados */
    out << "Q = {";
    set<int>::iterator itQ;
    for (itQ = afd._estados.begin(); itQ != afd._estados.end(); itQ++) {
        out << *itQ << ", ";
    }
    out << "}" << endl;

    /* Alfabeto */
    out << "A = {";
    set<char>::iterator itA;
    for (itA = afd._alfabeto.begin(); itA != afd._alfabeto.end(); itA++) {
        out << *itA << ", ";
    }
    out << "}" << endl;

    /* Transiciones */
    out << "s = {" << endl;
    AFD::mapTransicion::iterator itS;
    for (itS = afd._transiciones.begin(); itS != afd._transiciones.end();
                                                                    itS++) {
        out << "\t" <<  itS->first._estado << " x " << itS->first._caracter
            << " -> " << itS->second;
    }
    out << "}" << endl;

    /* Estado Inicial */
    out << "q = " << afd._inicial << endl;

    /* Estados Finales */
    out << "F = {";
    set<int>::iterator itF;
    for (itF = afd._finales.begin(); itF != afd._finales.end(); itF++) {
        out << *itF << ", ";
    }
    out << "}" << endl;

    return out;
}
